package weekMatch.two_107;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public class LeeCode_04 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(countServers(6, new int[][]{{1, 21}},
                10, new int[]{24, 35, 28, 26, 20, 25, 16, 31, 12})));
        System.out.println(Arrays.toString(countServers(3, new int[][]{{2, 26}, {3, 13}, {3, 1}},
                9, new int[]{28, 17})));
//        System.out.println(Arrays.toString(countServers(3, new int[][]{{1, 3}, {2, 6}, {1, 5}}, 5, new int[]{10, 11})));
    }

    private static int[] countServers(int n, int[][] logs, int x, int[] queries) {
        int[][] q = new int[queries.length][2];
        for (int i = 0; i < queries.length; i++) {
            q[i][0] = i;
            q[i][1] = queries[i];
        }
        Arrays.sort(q, Comparator.comparingInt(o -> o[1]));
        Arrays.sort(logs, Comparator.comparingInt(o -> o[1]));
        Map<Integer, Integer> map = new HashMap<>();
        int l = 0, r = 0;
        int[] ans = new int[queries.length];
        int m = logs.length;
        for (int[] ints : q) {
            int min = ints[1] - x, max = ints[1];
            while (r < m && logs[r][1] <= max){
                int id = logs[r][0];
                map.put(id, map.getOrDefault(id, 0) + 1);
                r++;
            }
            while (l < r && logs[l][1] < min){
                int id = logs[l][0];
                map.put(id, map.get(id) - 1);
                if (map.get(id) == 0)
                    map.remove(id);
                l++;
            }
            ans[ints[0]] = n - map.size();
        }
        return ans;
    }
}